1. Field of Invention
The present invention generally relates to communications systems connectivity, and in particular to a mechanism for path provisioning on ring-based networks.
2. Related Art
The availability of communication systems has become more and more important as different sectors of society increasingly utilize communication services such as voice, data, video and Internet traffic. As businesses and the general public become more dependent on these services, the availability requirement grows to an extent that is similar or higher than for other utility services. Moreover, different customers have different requirements in terms of cost and availability.
In the emerging field of deploying and providing high quality services, network operators are most interested in the ability to analyse the cost and availability of a path for providing the customers with reliable end-to-end connection at a minimum cost. The current generation of transport networks carry a high volume of traffic on fiber optics predominantly on SONET (synchronous optical network) transmission technology, and more recently on DWDM (dense wavelength division multiplexing) networks For example, an optical carrier OC-1 link carries more than 156,000 voice circuits or their equivalent, if rated at 64 kbps each. The unavailability of such a link may have a drastic impact on businesses and the community.
There are several ways to measure network integrity, namely restorability, reliability, and availability.
Restorability represents system""s ability to restore the traffic after failure, e.g. fiber/wire cut or equipment failure, within a target time, using restoration/rerouting mechanisms.
SONET architectures, like bi-directional line switched ring (BLSR) networks, or (1+1) linear networks, provide 100% restorability upon single element failure.
Reliability is the probability that a system or device will operate for a specified amount of time without a service-affecting failure.
Availability is a relevant measurement on cost-effectiveness and customer needs for quality end-to-end communications paths. End-to-end connections represent the main service offered by service providers, and the perception of quality of service (QoS) is based generally on the availability of this service.
Availability measures the ability of the network to continuously maintain traffic and reflects the probability that a system is operating satisfactorily at any randomly chosen, assuming an ongoing balance between failure and subsequent repairing.
The expression for network availability is:
A=MTBF/(MTBF+MTTR),
where MTBF is the mean time between failures, and MTTR is the mean time to repair.
If we note with xe2x80x9cUxe2x80x9d the normalized value of network unavailability, availability (A) may be determined by adding up all the unavailability (U) scenarios and calculating the network availability as A=1xe2x88x92U.
A simple point-to-point SONET transmission system consists of two network elements connected with fiber optic cables A network element is usually referred to as a xe2x80x9cnodexe2x80x9d, and the fiber link between two nodes (including any line regenerators) is referred to as a xe2x80x9cspanxe2x80x9d regardless of the number of physical fibers.
SONET uses dedicated protection facilities, so that in general 50%of the fiber and the equipment is used by the working traffic, and the remaining 50% is reserved for accommodating the traffic in case of failure. Thus, linear network architectures use (1+1), (1:1), or (1:N) protection schemes, while ring networks architectures use UPSR (unidirectional protection switched ring) and SLSR as protection mechanisms.
With the emerging WDM (wavelength division multiplexing) mesh traffic patterns become more popular. The mesh network topology is essentially a set of point-to-point links between nodes. Therefore, mesh networks generally use different protection protocols than linear and ring networks because there are usually at least two available paths between any two nodes. Thus, mesh restoration does not require dedicated protection and the spare capacities are shared for restoring affected connections.
End-to-end availability analysis of a path over a hypothetical ladder-like network is addressed by M. To and P. Neusy, xe2x80x9cUnavailability Analysis of Long-Haul Networksxe2x80x9d, IEEE Journal on Selected Areas in Communications, Vol.12, No.1, January 1994. The authors considered the availability of SONET and digital system DS3 as well as certain digital cross-connect restoration and end-to-end diversity routing. This study does not disclose path construction on ring networks and ring interconnection configurations.
W. D. Grover disclosed in xe2x80x9cAlternative Routing Strategies for High Availability Paths in SONET Ring Networks, TRLabs, January 1998, and in xe2x80x9cResource Management for Fault Tolerant Path Structures in SONET Ring Networksxe2x80x9d, JNSM 1997, June 1998, the mathematical model of availability for three mechanisms used to inter-connect rings, namely single-feeding (SF), matched-nodes (MN) and dual feeding (DF).
FIG. 1a illustrates an SF inter-ring configuration where the signal arriving on Ring-1 passes through an inter-ring connection 12 to Ring-2. Each inter-ring connection point 13 or 16, has an add-drop multiplexer (ADM) present at a common physical site, or point-of-presence (POP). These two ADMs are referred to as gateways. It is also possible to have more than one physical links 12, which implies a corresponding number of ADM pairs. The xe2x80x9ccross-office wiringxe2x80x9d connection 12 is used to connect the two gateways through ADMs. The SF cost is the lowest of the three inter-ring connection configurations. It is evident that a single element failure on inter-ring connection 12, will cause system outage and may dramatically reduce the end-to-end availability.
FIG. 1b illustrates an MN inter-ring configuration, having inter-ring connections 13, 15, as physical links between Ring-1 and Ring-2. There are two inter-ring gateway pairs namely W-Y and X-Z, with W and Y designated as the primary (P) gateways, and X and Z as the secondary (S) gateways.
In this configuration, the incoming signal from node A is dropped at node W to node Y, while the original signal continues to node X and passes to node Z using the inter-ring connection 16. The duplicated signal arriving at node Z from node Y is sent back to node Y and terminated if the primary inter-ring connection 13 is operational. If the inter-ring connection 15 is cut, the primary signal on line 13 is used. The MN configuration is redundant and protected from single-element and most dual-element failures, at the inter-ring connection site. However, the cost is considerably higher compared to the SF configuration.
As shown in FIG. 1c, in a DF inter-ring configuration, each inter-ring connection 17, 18, has two physical links between the two rings. The DF configuration uses two pairs of gateways [W-Y] and [X-Z] for each inter-ring connection point. Two copies of the same incoming signal travel through physical links 17 and 18, on paths (AWYB) and (VXZQ) without rejoining. The DF configuration is protected from all single-element and most dual-element (different set of combinations from MN) failures on inter-ring connection. Due to the duplication of signals, the DF configuration uses more bandwidth than the MN configuration. However, the DF configuration can cost less than the MN configuration particularly when rings are small or the distance between entry and egress nodes, e.g. W-Y or X-Z, is large.
FIGS. 2a, 2b, 2c, illustrate how the signal flows are configured at the inter-ring sites from an origin node (O) to a destination node (D) for single feeding (SF), matched nodes (MN), and dual feeding (DF) configurations, respectively.
There is a need for a path provisioning mechanism over survivable ring networks using combined matched-nodes (MN) and dual feeding (DF) configurations providing dual redundancy at the inter-ring connection site and cost/availability efficiency.
The present invention seeks to overcome the disadvantages of the prior art associated with inter-ring systems connectivity over ring-based networks.
According to one aspect of the invention, a method for provisioning a communications path between an origin node (O) and a destination node (D) in a bi-directional fine switched ring (BLSR) network, the xe2x80x9cOxe2x80x9d and xe2x80x9cDxe2x80x9d nodes being ascribed to a plurality of OD ring pairs, is provided The method comprises the steps of identifying an OD ring pair out of said plurality of OD ring pairs; selecting a ring sequence out of a plurality of valid ring sequences corresponding to the identified OD ring pair; calculating a current path associated with the selected ring sequence; comparing the current path with a current best path available from a database and continuously updating the database with the best current path; successively assigning inter-ring connection configurations and repeating steps (d) and (e) until a first communications path is obtained; repeating steps (b) to (e) for each valid ring sequence until a second communications path is obtained; and repeating steps (a) to (f) for each OD ring pair until an optimal path is found.
The ring sequence and/or the path construction reductions according to the present method provide for a practical decision in an acceptable period of time while maintaining the quality solutions set intact.
According to another aspect of the invention, a computer-readable medium containing computer executable instructions for performing the steps of the above method, is also provided.
According to a further aspect of the invention, there is provided an apparatus for path provisioning over SLSR networks including means for inputting path search requirements, means for calculating an optimal path between xe2x80x9cOxe2x80x9d and xe2x80x9cDxe2x80x9d nodes, and means for outputting the graph of the optimal path containing inter ring connection configurations and associated reporting data like the path cost (C), network unavailability (U), the strategy used for searching, and the elapsed time of the search.
Advantageously, the path provisioning apparatus of the invention provides an optimal O-D communications path in terms of cost ĉ and availability (U). The apparatus can provision the optimal communications path using a single objective optimization function like minC, or minU. If one of these parameters is used as a single objective optimization function with the other parameter used as a constraint, the mechanism of the present invention provides an optimal communications path in terms of either minimum cost with a maximum associated unavailability (minC/maxU), or minimum availability with a maximum associated cost (minU/maxC).
The present invention is not limited to the features disclosed in the xe2x80x9cSummary of the Inventionxe2x80x9d section; it nonetheless may reside on sub-combinations of the disclosed features.